\documentclass{article}
\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

% useful packages.
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{fancyhdr}
\usepackage{layout}
% \usepackage{ctex}
\usepackage{listings}
\usepackage{subfigure}
\usepackage{setspace}

% some common command
\newcommand{\dif}{\mathrm{d}}
\newcommand{\avg}[1]{\left\langle #1 \right\rangle}
\newcommand{\difFrac}[2]{\frac{\dif #1}{\dif #2}}
\newcommand{\pdfFrac}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\OFL}{\mathrm{OFL}}
\newcommand{\UFL}{\mathrm{UFL}}
\newcommand{\fl}{\mathrm{fl}}
\newcommand{\op}{\odot}
\newcommand{\Eabs}{E_{\mathrm{abs}}}
\newcommand{\Erel}{E_{\mathrm{rel}}}
\newcommand{\RNum}[1]{\uppercase\expandafter{\romannumeral #1\relax}}

\usepackage{xcolor}
\usepackage{fontspec} 
\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{comment}{rgb}{0.56,0.64,0.68}

\newfontfamily\monaco{Monaco}
\lstset {
aboveskip=3mm,
belowskip=3mm,
showstringspaces=false,       % underline spaces within strings
columns=flexible,
framerule=1pt,
rulecolor=\color{gray!35},
backgroundcolor=\color{gray!5},
basicstyle={\small\monaco},           % the size of the fonts that are used for the code
numbers=left,                   % where to put the line-numbers
numberstyle=\tiny\monaco\color{gray},  % the style that is used for the line-numbers
numbersep=5pt,                  % how far the line-numbers are from the code
commentstyle=\color{comment},
keywordstyle=\color{blue},
stringstyle=\color{dkgreen},
tabsize=2,                      % sets default tabsize to 2 spaces
captionpos=b,                   % sets the caption-position to bottom
breaklines=true,                % sets automatic line breaking
breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
escapeinside={\%*}{*)},            % if add LaTeX within your code
morekeywords={*,...}               % if add more keywords to the set
}


\begin{document}
\title{Homework \#5}
\pagestyle{fancy}
\lhead{Name Li HuiTeng 3180102114}
\chead{ NumAnalysis\#5}
\rhead{Date 21.12.07}

\section{Theoretical questions}

\RNum{1}
\begin{proof}
To prove $\mathcal{C}[a,b]$ furnished with 
$$
(u,v)=\int_a^b \rho(t)u(t)\bar{v}(t)dt
$$
is an inner product space: the real positivity and definiteness are owed to $\rho(x)>0$ on $(a,b)$. The other 
properties, i.e. additivity and homogeneity in the first slot, and conjugate symmetry, can be checked literally. \par 
To prove it's a normed vector space: such norm is induced from the above inner product, so just apply Lemma B.116. 
\end{proof}

\RNum{2}
\begin{proof}
$\forall m,n\in N$, 
\begin{align*}
  &\int_{-1}^{1}\frac{1}{\sqrt{1-x^2}}cos(m\text{arccosx})cos(n\text{arccosx})dx\\
  (p={arccosx})\quad &=\int_{0}^{\pi}cos(m\text{p})cos(n\text{p})dp\\
  &=\int_0^\pi \frac{1}{2}[cos((m-n)p)+cos((m+n)p)]dp\\
  &=\left\{\begin{array}{lc}0&m\neq n\\\mathrm\pi&m=n=0\\\mathrm\pi/2&m=n>0\end{array}\right.
\end{align*} 
Hence, by normalization, the fisrt three Chebyshev polynomials are to be 
\begin{align*}
  T_0(x)&=\frac{1}{\sqrt{\pi}}\\
  T_1(x)&=\frac{x}{\sqrt{\frac{\pi}{2}}}\\
  T_2(x)&=\frac{2x^2-1}{\sqrt{\frac{\pi}{2}}}.
\end{align*}
\end{proof}

\RNum{3}
\begin{proof}
For Fourier expansion,
\begin{align*}
b_0 &= \int_{-1}^{1}\frac{1}{\sqrt{1-x^2}}\sqrt{1-x^2}\frac{1}{\sqrt{\pi}}dx=\frac{2}{\sqrt{\pi}}\\
b_1 &= \int_{-1}^1\frac{1}{\sqrt{1-x^2}}\sqrt{1-x^2}\frac{x}{\sqrt{\frac{\pi}{2}}}dx=0\\
b_2 &= \int_{-1}^1\frac{1}{\sqrt{1-x^2}}\sqrt{1-x^2}\frac{2x^2-1}{\sqrt{\frac{\pi}{2}}}dx=-\frac{2}{3\sqrt{\frac{\pi}{2}}}
\end{align*}
we have $\widehat{\phi}_2=\frac{2}{\pi}-\frac{4(2x^2-1)}{3\pi}=-\frac{8}{3\pi}x^2+\frac{10}{3\pi}$. \par
For Normal expansion, choose from the linear independent list such as $(T_0,T_1,T_2)$ and construct the Gram matrix. Since $G(T_0,T_1,T_2)$ is an identity matrix (Lucky!), we then calculate the vector
\begin{align*}
c=\begin{bmatrix}<y,T_0>\\<y,T_1>\\<y,T_2>\end{bmatrix}
\end{align*}
Solve this trivial linear system and we have $(a_0,a_1,a_2)=(\frac{2}{\sqrt{\pi}},0,-\frac{2}{3\sqrt{\frac{\pi}{2}}})$,
which yields $\widehat{\phi}_2 = (T_0,T_1,T_2)\cdot(a_0,a_2,a_3)=-\frac{8}{3\pi}x^2+\frac{10}{3\pi}$.
\end{proof}

\RNum{4}
\begin{proof}
By Gram-Schmidt process,  
\begin{align}
u_1=1,v_1&=1,(v_1,v_1)=\sum_{i=1}^{12}1=12,v_1^*=\frac{1}{2\sqrt{3}}\\
u_2=x,v_2&=x-(x,1)1/12=x-\sum x_i=x-6.5,(v_2,v_2)=\sum(x_i-6.5)^2\\
&=\sum x_i^2-13x_i+6.5^2=650-13*78+12*6.5^2=143,v_2^*=\frac{x-6.5}{\sqrt{143}}\\
u_3=x^2,v_3&=x^2-(x^2,1)1/12-(x^2,x-6.5)*(x-6.5)/143\\
&=x^2-\frac{325}{6}-13(x-6.5)\\
&=x^2-13x+30.33333,\\
(v_3,v_3)&=\sum x_i^4-26x_i^3+(60.66667+169)x_i^2
-\frac{2366}{3}x_i+\frac{8281}{9}\\
&=60710-26*6084+(60.66667+169)*650-2366/3*78+8281/9*12\\
&=1.3347e+03,v_3^*=v_3/\sqrt{(v_3,v_3)}.
\end{align}
Then the orthonormal polynomials are 
\begin{align*}
  v_1^*&=0.2887\\
  v_2^*&=0.08362x-0.54356\\
  v_3^*&=0.0274x^2-0.3558x+0.8303
\end{align*}
For Fourier expansion, 
\begin{align}
  c_0 &= (y,v_1^*)=479.7781\\
  c_1 &= (y,v_2^*)=49.2023\\
  c_2 &= (y,v_3^*)=330.3304.
\end{align}
which yields $$\widehat{\phi}_2 = (T_0,T_1,T_2)\cdot(c_0,c_1,c_2) = 386.04-113.42x+9.05x^2.$$ 
$\widehat{\phi}$ is almost the same as that of the example and the difference is rather slight.

Suppose $x_i's$ are the same and $y_i's$ are different.
 Then as for Fourier Equation, the calculation for orthonormal polynomials, i.e. 
 equations $(1)\sim(9)$ can be reused; the calculation for 
 the Fourier coefficients, i.e. $(10)\sim(12)$, cannot be reused. 
 As for Normal Equation, the coefficient matrix can be reused.

This implies the advantage about dynamic optimization of Fourier Equation(FE) over Normal Equation(NE). 
When applied to a series of problems, FE only needs to work out the Fourier coefficients which is 
$O(n)$. However, NE needs to solve a $n\times n$ matrix equations again which is rather 
time-costly.
\end{proof}

\section{Programming}
Codes are contained in the e-mail tar, and only conclusions will be shown in the following part.
\subsection{\textbf{Assignment A}}
The following is a part from the output of running $\textbf{Assignment.m}$. 
\lstset{language=Matlab}
\begin{lstlisting}
  >> Assignment
  ------------------------Assignment A--------------------------
         2.1757
         2.6704
       -0.23844
\end{lstlisting}
Hence $\textbf{a}=(2.1757,2.6704,-0.23844)$, and then $p(x)=2.1757+2.6704x-0.23844x^2$.

\subsection{\textbf{Assignment B}}
The following is also a part from the output of running $\textbf{Assignment.m}$. 
\lstset{language=Matlab}
\begin{lstlisting}
  ------------------------Assignment B--------------------------
  2.1757
  2.6704
-0.23844

Cond(Gram)=18980.894284,Cond(R_1)=137.771166.
\end{lstlisting}
The result is the same, and we can see that the condition number of Gram matrix is 
much larger than that of $R_1$ via QR decomposition.
\end{document}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
